import functools


class Solution(object):
    def twoCitySchedCost(self, costs):
        n = len(costs)
        m = n // 2

        @functools.cache
        def search(i, j, k):
            if i == 0 and j == 0:
                return 0
            now_val = float('inf')
            if i > 0:
                now_val = min(search(i - 1, j, k - 1) + costs[k][0], now_val)
            if j > 0:
                now_val = min(search(i, j - 1, k - 1) + costs[k][1], now_val)
            return now_val
        return search(m, m, n - 1)

data = Solution()
costs = [[10, 20], [30, 200], [400, 50], [30, 20]]
print(data.twoCitySchedCost(costs))
